
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode firstNode = new ListNode(0);
        ListNode inNode = firstNode;
        ListNode lastNode = new ListNode(0);
        ListNode inNode2=lastNode;
        ListNode cur=pHead;
        while(cur!=null) {
            if(cur.val<x) {
                inNode.next=cur;
                inNode=inNode.next;
            } else {
                inNode2.next=cur;
                inNode2=inNode2.next;
            }
            cur=cur.next;
        }
        inNode.next=lastNode.next;
        inNode2.next=null;
        return firstNode.next;
    }
}
public class newcoder1 {
}
